그래프(Graph)

그래프

설명:

• 이 설명은 nnnyeong님의 블로그를 참고하여 정리하였다

그래프는 여러 개의 노드(node/vertices)와 노드가 간선(edge)로 이루어진 형태의 자료구조이다. 노드와 간선으로 이루어진 것은 트리와 흡사하지만 트리와는 다르게 순환이 가능하며 트리처럼 루트에서 시작하는 것이 아닌 딱히 시작점이 정해져 있지 않다. 그래프를 연결하는 간선이 방향이 있거나 가중치가 있는 등 다양한 방식으로 구현이 가능하다.

그래프를 구현하는 방법은 인접 행렬(adjacency matrix)와 인접 리스트(adjacency list)로 두가지 방법이 있다.

1. 인접 행렬은 2차원 배열로 구현하며 2차원 배열에 저장 되는 값은 두 노드 사이의 간선의 가중치이다. 만약에 가중치가 없을 경우에는 그냥 0, 1로 이어짐을 나타낸다.
2. 인접 리스트는 해싱할 때 데이터의 충돌을 막기 위해 채택 되는 저장 방식 중 하나인 seperate chaining 방식과 상당히 유사하다. 인접 리스트는 배열을 사용하여도 되고 벡터를 사용하여도 되고 사용 방식이 다양한데 결과적으로는 한가지 데이터 저장 공간에 해당 노드에 연결 되는 인접 노드를 저장해주는 방식이다.

또한, 그래프 자료구조를 탐색하는데 주로 BFS와 DFS 알고리즘을 사용한다. BFS 알고리즘은 넓이 우선 탐색이며 한단계 한단계 모든 인접노드를 확인하는 방면 DFS는 깊이 우선 탐색으로 인접한 노드에 연결 된 모든 모드를 끝까지 들어가서 확인하고 나오고를 반복한다.

1. BFS(Breadth First Search)(너비 우선 탐색): 큐를 사용하여 인접한 노드를 저장한 뒤 하나씩 꺼내서 차례대로 인접한 노드를 추가로 저장하는 방식을 이용한다.
2. DFS(Depth First Search)(깊이 우선 탐색): 재귀 함수를 사용하여 더 이상 방문할 수 있는 노드가 없을 때까지 인접한 노드를 탐색한다.

예시:

출처: https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/

예시 코드:

//그래프 구현 방식
#include <vector>

int graph[5][5] = {0};
vector<int> a[8];

int main(void){
	//인접 행렬 방식
	//0과 1를 연결합니다(배열의 위치가 노드의 번호에 해당 되며 저장값이 가중치인 방식)
	//해당 예시는 가중치가 없으므로 1과 0으로 연결 돼 있는지만 저장
	graph[0][1] = 1;
  graph[1][0] = 1;
	
	graph[0][4] = 1;
  graph[4][0] = 1;

	graph[1][2] = 1;
  graph[2][1] = 1;

	...
	//인접 리스트 방식
	//0과 1를 연결합니다(갖고 있는 이웃을 벡터에 저장하는 방식)
	a[0].push_back(1);
	a[1].push_back(0);

	a[0].push_back(4);
	a[4].push_back(0);

	a[1].push_back(2);
	a[2].push_back(1);

	...
}

//BFS 구현
#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
int number = 7;
int c[7];
vector<int> a[8];

void bfs(int start){
	queue<int> q;
	q.push(start);
	c[start] = true;
	while(!q.empty()){
		int x = q.front();
		q.pop();
		printf("%d ", x);
		for(int i = 0; i < a[x].size(); i++){
			int y = a[x][i];
			if(!c[y]){
				q.push(y);
				c[y] = true;
			}
		}
	}
}

//DFS 구현
#include <iostream>
#include <vector>

using namespace std;

int number = 7;
int c[7];
vector<int> a[8];

void dfs(int x){
	if(c[x]) return;
	c[x] = true;
	cout<< x <<' ';
	for(int i = 0; i < a[x].size(); i++){
		int y = a[x][i];
		dfs(y);
	}
}

문제 풀이:

🥉브론즈(Bronze):

🥈실버(Silver):

#2178: 미로 탐색

#4963: 섬의 개수

🥇골드(Gold):

👑플레티넘(Platinum):